home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / nelson / model-1a.c < prev    next >
C/C++ Source or Header  |  1990-05-25  |  5KB  |  140 lines
  1. /*
  2.  * Listing 16 -- model-1a.c
  3.  *
  4.  * This module is an order-1 fixed-context modeling unit that can
  5.  * be using in conjunction with comp-1.c and expand-1.c to compress
  6.  * and expand files.  It is a very simple implementation of an order-1
  7.  * model, using the same techniques for storing counts as were used
  8.  * in model-1.c.  This means that it uses a lot of memory, around
  9.  * 140 Kbytes, and that it spends a lot of time updating the table.
  10.  * Since it can loop up context tables with a simple index on the
  11.  * context character, it is still pretty fast.
  12.  *
  13.  * Building the compression and expansion programs with this model
  14.  * requires moving up to compact model.
  15.  *
  16.  * Building the compressor:
  17.  *
  18.  * Turbo C:     tcc -w -mc comp-1.c model-1a.c bitio.c coder.c
  19.  * QuickC:      qcl /AC /W3 comp-1.c model-1a.c bitio.c coder.c
  20.  * Zortech:     ztc -mc comp-1.c model-1a.c bitio.c coder.c
  21.  * *NIX:        cc -o comp-1 comp-1.c model-1a.c bitio.c coder.c
  22.  *
  23.  * Building the decompressor:
  24.  *
  25.  * Turbo C:     tcc -w -mc expand-1.c model-1a.c bitio.c coder.c
  26.  * QuickC:      qcl /AC /W3 expand-1.c model-1a.c bitio.c coder.c
  27.  * Zortech:     ztc -mc expand-1.c model-1a.c bitio.c coder.c
  28.  * *NIX:        cc -o expand-1 expand-1.c model-1a.c bitio.c coder.c
  29.  */
  30. #include <stdio.h>
  31. #include <stdlib.h>
  32. #include "coder.h"
  33. #include "model.h"
  34.  
  35. /*
  36.  * *totals[] is an array of pointers to context tables.  The EOF
  37.  * character doesn't get a context table, since we stop encoding
  38.  * as soon as that character appears.  Each context table is
  39.  * an array of ints with indices ranging from -1 to 255.
  40.  */
  41. short int *totals[ 256 ];
  42. /*
  43.  * context is the last character encoded or decoded.  It is
  44.  * used to index to the appropriate context table.  We start the
  45.  * model with an arbitray context of 0;
  46.  */
  47. int context = 0;
  48.  
  49. /*
  50.  * To initialize the model, I create all 256 context tables, and
  51.  * set all the counts in the table to 1.  By default, the model
  52.  * starts up in context 0, as if the last byte in was '\0'.  Since
  53.  * each context table is supposed to be indexed from -1 to 255,
  54.  * I increment the pointer to the table in totals[], so that the
  55.  * array can be safely indexed with -1.
  56.  */
  57. void initialize_model()
  58. {
  59.     int i;
  60.     short int j;
  61.     int array_size;
  62.  
  63.     array_size = sizeof( short int * ) * ( 257 + 1 );
  64.     for ( i = 0 ; i < 256 ; i++ )
  65.     {
  66.         totals[ i ] = (short int *) malloc( array_size ) ;
  67.         if ( totals[ i ] == NULL )
  68.         {
  69.             printf( "Error allocating table space!\n" );
  70.             exit( 1 );
  71.         }
  72.         totals[ i ]++;
  73.         for ( j = -1 ; j <= 256 ; j++ )
  74.             totals[ i ][ j ] = j + 1;
  75.     }
  76. }
  77.  
  78. /*
  79.  * When the table is updated, every count above "symbol" needs to
  80.  * be incremented, which is somewhat expensive.  If the counts
  81.  * have become to large, the table needs to be rescaled.  While
  82.  * rescaling, we have to make sure that none of the counts drop
  83.  * below 1.  After the update is complete, the context is changed
  84.  * to be the symbol that was just updated.
  85.  */
  86. void update_model( int symbol )
  87. {
  88.     int i;
  89.  
  90.     for ( i = symbol+1 ; i <= 256; i++ )
  91.         totals[ context ][ i ]++;
  92.     if ( totals[ context ][ 256 ] == MAXIMUM_SCALE )
  93.     {
  94.         for ( i = 0 ; i <= 256 ; i++ )
  95.     {
  96.             totals[ context ][ i ] /= 2;
  97.             if ( totals[ context ][ i ] <= totals[ context ][ i-1 ])
  98.                 totals[ context ][ i ] = totals[ context ][ i-1 ] + 1;
  99.     }
  100.     }
  101.     context = symbol;
  102. }
  103.  
  104. /*
  105.  * Since the context table can be directly indexed with the
  106.  * symbol, getting the low and high counts for the particular
  107.  * symbol is nice and easy.
  108.  */
  109. int convert_int_to_symbol( int c, SYMBOL *s )
  110. {
  111.     s->scale = totals[ context ][ 256 ];
  112.     s->low_count = totals[ context ][ c ];
  113.     s->high_count = totals[ context ][ c + 1 ];
  114.     return( 0 );
  115. }
  116. /*
  117.  * The symbols scale is always in the same place, which is nice.
  118.  */
  119. void get_symbol_scale( SYMBOL *s )
  120. {
  121.     s->scale = totals[ context ][ 256 ];
  122. }
  123. /*
  124.  * To find the symbol whose low and high values straddle count
  125.  * requires walking through the table until a match is found.
  126.  * This is a lengthy operation, and helps to keep decoding
  127.  * slower than encoding.
  128.  */
  129. int convert_symbol_to_int( int count, SYMBOL *s )
  130. {
  131.     int c;
  132.  
  133.     for ( c = 256; count < totals[ context ][ c ] ; c-- )
  134.         ;
  135.     s->high_count = totals[ context ][ c + 1 ];
  136.     s->low_count = totals[ context ][ c ];
  137.     return( c );
  138. }
  139.  
  140.